Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи №2 з дисципліни “Дискретні структури ” Виконав: студент групи ПІ – 2 Львів 2008 Тема.Елементи комбінаторики. Біном Ньютона. Методи комбінаторного аналізу Мета. Навчитись використовувати методи комбінаторного аналізу Завдання Обчислення кількості комбінацій розміщення (перестановок, комбінацій, алгоритму визначення наступної лексикографічної сполуки, перестановки) та формулу бінома Ньютона і побудувати за допомогою неї розклад. Задане додатне ціле число n і невід’ємне ціле число r, (r<=n). Розташувати у лексикографічному порядку всі сполуки без повторень із r елементів множини {1,2,…,n}. Побудувати розклад (x-y)5. Текст програми #include <iostream> #include <conio.h> using namespace std; int fact(int n) { int res=1; for(int i=1;i<=n;i++) res=res*i; return res; } int main() { int s,n,C=0; int spol[100]; cout<<"Vvedit` stepin` Binjoma Njutona:\n"; cin>>s; cout<<"\nBinjom Njutona pow((x-y),"<<s<<"):\n\n"; for (int i=0;i<=s;i++) { if(i!=s) cout<<"(-1)^"<<i<<" * "<<fact(s)/(fact(i)*fact(s-i))<<" * (x^"<<i<<" * y^"<<s-i<<") + "; else cout<<"(-1)^"<<i<<" * "<<fact(s)/(fact(i)*fact(s-i))<<" * (x^"<<i<<" * y^"<<s-i<<") "; } for(int i=1;i<101;i++) spol[i]=i; cout<<"\nVvedit` kil`kist` elementiv u spoluci:\n"; cin>>n; cout<<"\nZagal`na kil`kist` mozhlyvyh spoluchen` bez povtoren` stanovyt`: "; for(int r=0;r<n;r++) { C=C+fact(n)/(fact(r)*fact(n-r)); } cout<<C; cout<<"\nSpoluky bez povtoren`:\n"; for(int i=1;i<=n;i++) { cout<<" ["<<spol[i]<<"]" ; for(int r=i;r>=1;r--) { if(spol[i]!=spol[r]) { cout<<" ["<<spol[r]<<";"<<spol[i]<<"] "; } } } if (n==3) cout<<" ["<<spol[1]<<";"<<spol[2]<<";"<<spol[3]<<"]" ; getche (); } Протокол виконання
Висновок : Ознайомились з основними елементами комбінаторики. Виконав завдання згідно варіанту.